package cn.edu.jxau.test;

import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * 基于小顶堆的索引优先队列
 * 
 * @author 付大石
 */
public class IndexMinPQ<T extends Comparable<T>> {
    
    
    /**
     * 堆到elementArr的映射
     */
    private int[] pq;

    /**
     * elementArr到堆的映射
     */
    private int[] qp;

    /**
     * 数据集
     */
    private T[] elementArr;

    /**
     * 元素个数
     */
    private int size;

    public IndexMinPQ(int capacity) {

        pq = new int[capacity + 1];
        qp = new int[capacity + 1];
        elementArr = (T[]) new Comparable[capacity];

        for (int i = 0; i < pq.length; i++) {
            pq[i] = -1;
            qp[i] = -1;
        }
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public boolean contains(int i) {
        return qp[i] != -1;
    }

    /**
     * 获取最小元素的索引
     * @return
     */
    public int minIndex() {

        if (isEmpty()) {
            throw new RuntimeException("优先队列为空");
        }
        return pq[1];
    }

    /**
     * 获取最小的元素
     * @return
     */
    public T min() {

        if (isEmpty()) {
            throw new RuntimeException("优先队列为空");
        }
        return elementArr[pq[1]];
    }

    public void insert(int i, T element) {

        if (i < 0 || i >= elementArr.length) {
            throw new IndexOutOfBoundsException("i=" + i);
        }
        if (contains(i)) { // 已存在
            change(i, element);
            return ;
        }
        elementArr[i] = element;
        size++;
        pq[size] = i;
        qp[i] = size;
        swim(size);
    }

    public void change(int i, T element) {

        if (i < 0 || i >= elementArr.length) {
            throw new IndexOutOfBoundsException("i=" + i);
        }
        if (!contains(i)) {
            throw new NoSuchElementException("i=" + i + ",其指定的元素不存在");
        }
        T old = elementArr[i];
        elementArr[i] = element;
        if (old.compareTo(element) < 0) { // 变大了
            sink(qp[i]);
        } else if (old.compareTo(element) > 0) { // 变小了
            swim(qp[i]);
        }
    }

    /**
     * 删除最小元素，并返回其索引
     * @return
     */
    public int delMin() {

        if (isEmpty()) {
            throw new RuntimeException("优先队列为空");
        }
        int minIndex = minIndex();
        delete(minIndex);
        return minIndex;
    }

    public T delete(int i) {

        if (!contains(i)) {
            throw new RuntimeException("要删除的元素不存在");
        }
        T ret = elementArr[i];
        int k = qp[i];
        swap(k, size--);
        sink(k);
        swim(k);
        elementArr[i] = null; // 对象游离
        qp[i] = -1;
        pq[size + 1] = -1;
        return ret;
    }

    private void swim(int k) {

        while (k > 1 && elementArr[pq[k]].compareTo(elementArr[pq[k / 2]]) < 0) { // 子元素小于父元素
            swap(k, k / 2);
            k = k / 2;
        }
    }

    private void sink(int k) {

        while (2 * k <= size) {
            int i = 2 * k;
            if (i + 1 <= size && elementArr[pq[i]].compareTo(elementArr[pq[i + 1]]) > 0) { // 找出子元素中较小的一个
                i++;
            }
            if (elementArr[pq[k]].compareTo(elementArr[pq[i]]) <= 0) {
                break;
            }
            swap(k, i);
            k = i;
        }
    }

    private void swap(int i, int j) {

        int temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;

        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }
    
    @Override
    public String toString() {
        
        StringBuilder builder = new StringBuilder();
        builder.append(Arrays.toString(pq)).append("\n").append(Arrays.toString(qp)).append("\n");
        builder.append(Arrays.toString(elementArr)).append("\n");
        return builder.toString();
        
    }
}
